/**

 * Creates an BinaryTree.
 * Inherit from Cloneable
 * @author	Wan Changhua
 * @version	2.01, 10/23/05 $Id: BinaryTree.js 35 2008-03-02 17:01:34Z dsonet $
 * @extends Cloneable
 * @class This is the BinaryTree class.
 * @constructor
 */
function BinaryTree(data)
{
	if (data)
	{
		this.add(data);
	}
}
var $p = Type.extend(BinaryTree, Cloneable).prototype;

$p.count = 0;
$p.root = null;

$p.add = function(data)
{
	var n = new Node(data)
		, i
		, current = this.root
		, parent = null;

	while (current)
	{
		i = current.compare(n);

		if (i == 0)
		{
			return;
		}
		parent = current;
		i > 0 ? current = current.left : current = current.right;
	}
	this.count++;

	if (!parent)
	{
		this.root = n;
	}
	else
	{
		i = parent.compare(n);
		i > 0 ? parent.left = n : parent.right = n;
	}
};
$p.clear = function()
{
	this.root = null;
	this.count = 0;
};
$p.clone = function()
{
	var c = BinaryTree(), itr = this.getIterator();

	while (itr.hasNext())
	{
		c.add(itr.next());
	}
	return c;
};
$p.contains = function(data)
{
	return this.search(data) != null;
};
$p.remove = function(data)
{
	var current = root
		, parent = null
		, i = current.compareValue(data);

	while (i != 0 && current != null)
	{
		if (i > 0)
		{
			parent = current;
			current = current.left;
		}
		else if (i < 0)
		{
			parent = current;
			current = current.right;
		}
		i = current.compareValue(data);
	}

	if (!current)
	{
		return;
	}
	this.count--;

	if (!current.right)
	{
		if (!parent)
		{
			root = current.left;
		}
		else
		{
			i = parent.compare(current);

			if (i > 0)
			{
				parent.left = current.left;
			}
			else if (i < 0)
			{
				parent.right = current.left;
			}
		}
	}
	else if (!current.right.left)
	{
		if (!parent)
		{
			root = current.right;
		}
		else
		{
			i = parent.compare(current);

			if (i > 0)
			{
				parent.left = current.right;
			}
			else if (i < 0)
			{
				parent.right = current.right;
			}
		}
	}
	else
	{
		var leftmost = current.right.left
			, lmParent = current.right;

		while (leftmost.left != null)
		{
			lmParent = leftmost;
			leftmost = leftmost.left;
		}
		lmParent.left = leftmost.right;
		leftmost.left = current.left;
		leftmost.right = current.right;

		if (!parent)
		{
			root = leftmost;
		}
		else
		{
			i = parent.compare(current);

			if (i > 0)
			{
				parent.left = leftmost;
			}
			else if (i < 0)
			{
				parent.right = leftmost;
			}
		}
	}
};
$p.getIterator = function(current, arr)
{
	if(arguments.length < 2)
		return new Iterator(this.getIterator(this.root, []));
	if (current)
	{
		this.getIterator(current.left, arr);
		arr.push(current.value);
		this.getIterator(current.right, arr);
	}
};
this.search = function(current, data)
{
	if(arguments.length < 2)
		data = current, current = this.root;
	if (!current)
	{
		return null;
	}
	var i = current.compareValue(data);

	if (i == 0)
	{
		return current;
	}
	return this.search(i > 0 ? current.left : current.right, data);
};
this.toString = function(order, sep)
{
	var TraversalMethods = BinaryTree.TraversalMethods, s = "";
	if (!order)
	{
		order = TraversalMethods.Inorder;
	}

	if (!sep)
	{
		sep = ",";
	}

	switch (order)
	{
		case TraversalMethods.Preorder:
			s = preorderTraversal(this.root, sep);
			break;

		case TraversalMethods.Inorder:
			s = inorderTraversal(this.root, sep);
			break;

		case TraversalMethods.Postorder:
			s = postorderTraversal(this.root, sep);
			break;
	}
	;

	if (s.length == 0)
	{
		return "";
	}
	else
	{
		return s.substring(0, s.length - sep.length);
	}
};
BinaryTree.TraversalMethods =
{
	Preorder : 1,
	Inorder : 2,
	Postorder : 3
};

function preorderTraversal(current, sep)
{
	var s = "";

	if (current)
	{
		s = current.value.toString() + sep;
		s += preorderTraversal(current.left, sep);
		s += preorderTraversal(current.right, sep);
	}
	return s;
}

function inorderTraversal(current, sep)
{
	var s = "";

	if (current)
	{
		s = inorderTraversal(current.left, sep);
		s += current.value.toString() + sep;
		s += inorderTraversal(current.right, sep);
	}
	return s;
}

function postorderTraversal(current, sep)
{
	var s = "";

	if (current)
	{
		s = postorderTraversal(current.left, sep);
		s += postorderTraversal(current.right, sep);
		s += current.value.toString() + sep;
	}
	return s;
}

function Node(data, rNode, lNode){
	this.value = data || null;
	this.right = rNode || null;
	this.left = lNode || null;
}

$p = Type.extend(Node, Cloneable).prototype;

$p.clone=function()
{
	var c = new Node, v = this.value;
	c.value = v.value ? v.clone() : v;
	if(this.left != null)
	{
		c.left = this.left.clone();
	}
	if(this.right != null)
	{
		c.right = this.right.clone();
	}
	return c;
}
$p.compare=function(n)
{
	return this.value > n.value ? 1 : this.value < n.value ? -1 : 0;
}
$p.compareValue=function(d)
{
	return this.value > d ? 1 : this.value < d ? -1 : 0;
}
$p = null;